/*
 * Tree.java
 *
 * Created on 2007年10月14日, 下午12:54
 *
 * To change this template, choose Tools | Template Manager
 * and open the template in the editor.
 */
package com.exclamation.util.graph;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 *
 * @author littlerock
 */
public class Tree implements Graph {

    protected ArrayList<TreeNode> nodes = new ArrayList<TreeNode>();
    protected ArrayList<Edge> es = new ArrayList<Edge>();
    protected GraphImp graph;
    protected TreeNode root;

    /** Creates a new instance of Tree */
    public Tree() {
        graph = new SimpleGraphImp();
        root = createNode(null);
    }

    public boolean isDirected() {
        return graph.isDirected();
    }

    public Vertex[] getVertexes() {
        List<Vertex> nv = new LinkedList<Vertex>();
        for (Vertex v : this.nodes) {
            if (v != null) {
                nv.add(v);
            }
        }
        Vertex[] reVal = new Vertex[nv.size()];
        return nv.toArray(reVal);
    }

    public Edge[] getEdges() {
        List<Edge> ne = new LinkedList<Edge>();
        for (Edge e : es) {
            if (e != null) {
                ne.add(e);
            }
        }
        Edge[] reVal = new Edge[ne.size()];
        return ne.toArray(reVal);
    }

    public Vertex getVertex(int v) {
        try {
            return nodes.get(v - 1);
        } catch (Exception e) {
            return null;
        }
    }

    public Edge getEdge(int e) {
        try {
            return this.es.get(e - 1);
        } catch (Exception ex) {
            return null;
        }
    }

    public TreeNode getNode(int v) {
        try {
            return nodes.get(v - 1);
        } catch (Exception e) {
            return null;
        }
    }

    public TreeNode root() {
        return this.root;
    }

    public int height() {
        return this.root.height();
    }

    public TreeNode addNode(int father) {
        if (father == 0) {
            TreeNode node = createNode(null);
            root.setFather(node);
            this.root = node;
            return node;
        }

        if (this.getVertex(father) == null) {
            return null;
        }
        return createNode((TreeNode) this.getVertex(father));

    }

    public boolean changeFather(int n, int newFather) {
        if (this.getNode(n) == null || this.getNode(newFather) == null) {
            return false;
        } else {
            return this.getNode(n).setFather(this.getNode(newFather));
        }
    }

    public boolean removeNode(int n) {
        if (this.getNode(n) == null) {
            return false;
        }
        return this.getNode(n).remove();

    }

    public String toString() {
        return this.graph.toString();

    }

    private TreeNode createNode(TreeNode father) {
        Vertex v = graph.addVertex();
        TreeNode reVal = new TreeNode(v, this, father);
        this.nodes.add(reVal);
        return reVal;
    }

    private int addEdge(int tail, int head) {
        Edge e = graph.addEdge(tail, head);
        this.es.add(new TreeEdge(e));
        return e.getId();
    }

    private void removeEdge(int e) {
        this.es.set(e - 1, null);
        this.graph.removeEdge(e);
    }

    private void removeNode(TreeNode n) {
        this.nodes.set(n.getId() - 1, null);
        System.out.println("Remove Node " + n.getId() + ": " + this.getNode(n.getId()));
        this.graph.removeVertex(n.getId());

    }

    public static class TreeNode implements Vertex {

        Vertex v;
        Tree t;
        TreeNode father;
        int fatherEdge;
        LinkedList<TreeNode> children = new LinkedList<TreeNode>();

        TreeNode(Vertex v, Tree t, TreeNode father) {
            this.t = t;
            this.v = v;
            this.setFather(father);
        }

        public int getId() {
            return v.getId();
        }

        public Object getValue() {
            return v.getValue();
        }

        public void setValue(Object value) {
            v.setValue(value);
        }

        public Edge[] getOutEdges() {
            Edge[] edges = v.getOutEdges();
            Edge[] reVal = new Edge[edges.length];
            int i = 0;
            for (Edge e : edges) {
                reVal[i++] = t.es.get(e.getId());
            }
            return reVal;
        }

        public Edge[] getInEdges() {
            Edge[] edges = v.getInEdges();
            Edge[] reVal = new Edge[edges.length];
            int i = 0;
            for (Edge e : edges) {
                reVal[i++] = t.es.get(e.getId());
            }
            return reVal;
        }

        public Edge[] getEdges() {
            Edge[] edges = v.getEdges();
            Edge[] reVal = new Edge[edges.length];
            int i = 0;
            for (Edge e : edges) {
                reVal[i++] = t.es.get(e.getId());
            }
            return reVal;
        }

        public Graph getGraph() {
            return t;
        }

        public TreeNode father() {
            return this.father;
        }

        public List<TreeNode> children() {
            return this.children;
        }

        public TreeNode child(int index) {
            try {
                return this.children.get(index - 1);
            } catch (Exception e) {
                return null;
            }
        }

        public int getChildrenIndex(int v) {
            int i = 0;
            for (TreeNode node : children) {
                i++;
                if (node.getId() == v) {
                    return i;
                }
            }
            return 0;
        }

        public boolean isRoot() {
            return this.father == null;
        }

        public boolean isLeaf() {
            return this.children.size() == 0;
        }

        public boolean isAncestorOf(int v) {
            if (this.getId() == v) {
                return true;
            }
            if (this.isLeaf()) {
                return false;
            } else {
                for (TreeNode node : children) {
                    if (node.isAncestorOf(v)) {
                        return true;
                    }
                }
            }
            return false;
        }

        public boolean isDescendantOf(int v) {
            if (this.getId() == v) {
                return true;
            }
            if (this.isRoot()) {
                return false;
            } else {
                return this.father.isDescendantOf(v);
            }
        }

        public int height() {
            if (this.isLeaf()) {
                return 0;
            }
            int max = 0;
            int temp = 0;
            for (TreeNode child : children) {
                temp = child.height();
                if (temp > max) {
                    max = temp;
                }
            }
            return max + 1;
        }

        public int depth() {
            if (this.isRoot()) {
                return 0;
            } else {
                return 1 + this.father.depth();
            }
        }

        public int level() {
            return t.height() - this.depth();
        }

        public void setChildIndex(int src, int dest) {
            if (this.children.size() < dest) {
                return;
            }
            TreeNode node = this.children.remove(src - 1);
            if (node == null) {
                return;
            }
            this.children.add(dest - 1, node);

        }

        public TreeNode addChild() {
            return t.addNode(this.getId());
        }

        public TreeNode addChild(TreeNode n) {
            if (n == null) {
                return null;
            }
            if (n.setFather(this)) {
                return n;
            } else {
                return null;
            }
        }

        public boolean setFather(TreeNode newFather) {
            if (this.father == newFather || newFather == null) {
                return false;
            }
            if (this.isAncestorOf(newFather.getId())) {
                return false;
            }
            if (this.father != null) {
                this.t.removeEdge(this.fatherEdge);
                father.children().remove(this);
            }


            int e = t.addEdge(newFather.getId(), this.getId());
            this.father = newFather;
            this.fatherEdge = e;
            newFather.children().add(this);
            return true;
        }

        public boolean remove() {
            if (this.isRoot()) {
                return false;
            }
            TreeNode[] cs = new TreeNode[this.children.size()];
            this.children.toArray(cs);
            for (TreeNode c : cs) {
                c.remove();
            }
            this.t.removeEdge(this.fatherEdge);
            this.father.children.remove(this);
            this.father = null;
            this.fatherEdge = 0;

            this.children = null;
            this.t.removeNode(this);
            return true;
        }
    }

    class TreeEdge implements Edge {

        Edge e;

        TreeEdge(Edge e) {
            this.e = e;
        }

        public boolean isDirected() {
            return e.isDirected();
        }

        public int getId() {
            return e.getId();
        }

        public Object getValue() {
            return e.getValue();
        }

        public void setValue(Object value) {
            e.setValue(value);
        }

        public Vertex getTail() {
            return Tree.this.getVertex(e.getTail().getId());
        }

        public Vertex getHead() {
            return Tree.this.getVertex(e.getHead().getId());
        }

        public Graph getGraph() {
            return Tree.this;

        }
    }
}
